package hw;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class TheWorseProduct {

    public static void main(String[] args) {
        TheWorseProduct theWorseProduct = new TheWorseProduct();
        int[] ints = theWorseProduct.theWorseProduct(new int[]{12,3,3,5,6,8,9,10,3, 3, 8, 6, 5, 4}, 5);
        System.out.println(Arrays.toString(ints));
    }

    public int[] theWorseProduct(int[] products, int m) {
        // 使用一个队列存放最小的数，如果最小的数存在多个，就放多个
        int length = products.length;
        int[] results = new int[length - m + 1];
        Deque<Integer> eq = new LinkedList<>();
        for (int i = 0; i < length; i++) {
            if (i >= m) {
                // 开始输出最小数,最早的先输出
                results[i - m] = eq.peekFirst();
                if (products[i - m] == eq.peekFirst()) {
                    eq.removeFirst();
                }
            }
            while (!eq.isEmpty() && eq.peekLast() > products[i]) {
                eq.removeLast();
            }
            eq.addLast(products[i]);
        }
        results[length - m] = eq.peekFirst();
        return results;
    }

}
